package com.leetcode.普通数组;

//最大子数组和
public class lc_53 {
    public static void main(String[] args) {

    }

    //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    //子数组是数组中的一个连续部分。
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        //初始化当前子数组和目前为止最大子数组和,至少为一个元素
        int currentSum = nums[0]; //当前子数组的和
        int maxSum = nums[0]; //到目前为止找到的最大子数组和

        for (int i = 1; i < nums.length; i++){
            //如果此时前面的和为负数,证明后面继续带着此时的currentSum是没有益处的,直接开始一个新的数组
            //[-2,1,-3,4,-1,2,1,-5,4]  元素位置 1, 3, 5 会开始一个新数组
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            //更新最大数组
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}
